/**
 * 28. Implement strStr()
 * https://leetcode.com/problems/implement-strstr/
 */
package lc28;

public class Main {
  public static void main(String[] args) {
    String haystack = "misisippi";
    String needle = "isip";
    int p = new Solution().strStr(haystack, needle);
    System.out.println(p);
  }
}

class Solution { // 7ms
  public int strStr(String haystack, String needle) {
    if (needle.length() == 0) return 0;

    int cursor = 0;
    char[] ha = haystack.toCharArray();
    char[] na = needle.toCharArray();
    for (int i = 0; i < ha.length; i++) {
      if (ha[i] == na[cursor]) {
        if (++cursor == na.length) {
          return i - cursor + 1;
        }
      } else {
        i -= cursor;
        cursor = 0;
      }
    }
    return -1;
  }
}

class Solution2 { // 11ms
  public int strStr(String haystack, String needle) {
    int nl = needle.length();
    if (nl == 0) return 0;

    int hl = haystack.length();
    int cursor = 0;
    for (int i = 0; i < hl; i++) {
      if (haystack.charAt(i) == needle.charAt(cursor)) {
        if (++cursor == nl) {
          return i - cursor + 1;
        }
      } else {
        i -= cursor;
        cursor = 0;
      }
    }
    return -1;
  }
}
